package basic.courseLearn13.treeDp;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

//派对快乐值问题，求解最大的排队快乐值
public class PartyHappy {

    //员工
    private class Employee {
        public int happy; //开心值
        List<Employee> subordinates; //下属

        public Employee(int happy) {
            this.happy = happy;
            subordinates = new ArrayList<>();
        }
    }

    @Test
    public void test_maxHappy() {
        Employee node1 = new Employee(1);

        Employee node2 = new Employee(3);
        Employee node3 = new Employee(5);

        Employee node4 = new Employee(7);
        Employee node5 = new Employee(2);
        Employee node6 = new Employee(3);
        Employee node7 = new Employee(1);

        node1.subordinates.add(node2);
        node1.subordinates.add(node3);

        node2.subordinates.add(node4);
        node2.subordinates.add(node5);
        node3.subordinates.add(node6);
        node3.subordinates.add(node7);

        System.out.println("最大快乐值："+maxHappy(node1, 0));
    }


    /**
     * 利用树形dp求解最大快乐值问题
     * @param root 根节点
     * @param currentHappy 当前节点的快乐值
     * @return 最大快乐值
     */
    public int maxHappy(Employee root,int currentHappy) {
        //1. 递归终止条件
        if (root == null){
            return 0;
        }
        //2. 根据左右节点判断
        //2.1 该节点来
        int come = root.happy + currentHappy;
        //2.2 该节点不来
        int notCome = currentHappy;
        for (Employee subordinate : root.subordinates) {
            notCome += maxHappy(subordinate, 0);
        }
        //3. 取最大值
        return Math.max(come, notCome);

    }




}
